洛谷 P7922 [Kubic] Pyramid 题解
题目链接
给定一个初始长度为 nnn 的序列 ppp。
设当前 ppp 的长度为 LLL，有以下两种操作：
A 操作先构造长度为 L−1L-1L−1 的序列 p′p'p′ 满足 pi′=min{pi,pi+1},i∈[1,L)p_i'=\min\{p_i,p_{i+1}\},i\in [1,L)pi′=min{pi,pi+1},i∈[1,L)。然后用 p′p'p′ 代替 ppp。
B 操作先构造长度为 L−1L-1L−1 的序列 p′p'p′ 满足 pi′=max{pi,pi+1},i∈[1,L)p_i'=\max\{p_i,p_{i+1}\},i\in [1,L)pi′=max{pi,pi+1},i∈[1,L)。然后用 p′p'p′ 代替 ppp。
再给定一个长度为 mmm 的序列 aaa，表示一共进行 mmm 组操作，第 iii 组中先进行 aia_iai 次 A 操作，再进行 aia_iai 次 B 操作。保证 2∑ai=n...
符号与约定
在本文中：
字符串索引默认从 111 开始。
用 s[l,r]s_{[l, r]}s[l,r] 表示子串 slsl+1sl+2…srs_l s_{l + 1} s_{l + 2} \ldots s_rslsl+1sl+2…sr，特别地，当 [l,r]=∅[l, r] = \varnothing[l,r]=∅ 时表示空串。
用 pre(s,i)\mathrm{pre}(s, i)pre(s,i) 表示 s[1,i]s_{[1, i]}s[1,i]，suf(s,i)\mathrm{suf}(s, i)suf(s,i) 表示 s[i,∣s∣]s_{[i, |s|]}s[i,∣s∣]。
定义
对于一个字符串 sss，若正整数 i<∣s∣i<|s|i<∣s∣ 满足 pre(s,i)=suf(s,∣s∣−i+1)\mathrm{pre}(s, i) = \mathrm{suf}(s, |s| - i + 1)pre(s,i)=suf(s,∣s∣−i+1)，则称 pre(s,i)\mathrm{pre}(s, i)pre(s,i) 为 sss 的...
Legacy
TopCoder XorBoard
给定 H,W,R,C,SH, W, R, C, SH,W,R,C,S，给一个 H×WH \times WH×W 的网格，初始全为白色，每次可以选一列或选一行白变黑、黑变白，问行操作 RRR 次，列操作 LLL 次，最终黑色面积为 SSS 的方案数。两种操作不同当且仅当存在一行或一列被操作的次数不同。
枚举染了几行几列然后算方案数即可。
TopCoder ConversionMachine
给定两个字符集为 {a,b,c}\{\texttt{a},\texttt{b},\texttt{c}\}{a,b,c} 的字符串 s,ts, ts,t，每次操作可以对 sss 的某个位置的字符向后变一位，给出每个字符变成下一个字符的代价和最大代价问把 sss 变成 ttt 的方案数。
每个位置都是先还原后再进行若干组 a→b→c→a\texttt{a} \to \texttt{b} \to \texttt{c} \to \texttt{a}a→b→c→a 的轮换，所以可以确定总的操作次数上限，然后设 dpi,jdp _ {i, j}...
Day1T1 季风 wind
Link
Day1T2 魔法手杖 xor
考虑扔 Trie 上，然后在 Trie 上游走，表示当前 U∖SU \setminus SU∖S 中 ⊕x{} \oplus x⊕x 后最小的值。
然后考虑往某个儿子走，若要 mini∈U∖Sai⊕x\min _ {i \in U \setminus S} a _ i \oplus xmini∈U∖Sai⊕x 这一位是 111 则需要把另一个儿子扔到 SSS 里，但是当走 111 的时候不一定 mini∈U∖Sai⊕x\min _ {i \in U \setminus S} a _ i \oplus xmini∈U∖Sai⊕x 这一位是 111 答案就更优，那这种情况就需要两种都跑一遍。
以上是考场想法。
考虑二分答案，这样就可以直接贪做到 O(nk2)O(n k ^ 2)O(nk2)，用压缩 Trie 可以优化到 O(nk)O(nk)O(nk)，但是毛想想就知道很难写。
不妨直接考虑最终答案，若答案这一位需要是 111，则除了 mini∈U∖Sai⊕x\min _ {i \in U \se...
连夜赶的，等有时间再稍微润色一下（
Day -1
Lynkcat & zhh 逆天模拟赛，没想到省选最后一次模拟赛还吃了依托大的。
然而竟然打到了比较高的名次，果然我只会打答辩场啊……
但是不得不说确实涨信心了（
Day 0
上午不想写题了，鉴赏了几首 hitorie 的歌，然后写了个凸包板子就去吃午饭了。
下午一点上车去杭州，车上看了一下洛谷省选计划的模拟赛题，然后打算听会歌，结果耳机没连上直接外放了！！！当场社死。
到酒店之后借 Gold 的板子打了会 Phigros。
（这里应该有一张图）
好评如潮，说明我省选会打得非常好（确信。
然后出去吃了个晚饭，晚上又看了一下之前校内模拟赛的题，发现有些题一点印象都没了。
看完之后继续打摆，最后复习了一下矩阵相关就睡觉了。
Day 1
杭师大的显示屏终于不是傻逼的 4 : 3 了，感动中国！
先看完三个题然后开始做 T1，看数据范围就知道是 O(n)O(n)O(n) 的，然后就考虑对于答案 mod n{} \bmod nmodn 同余的部分放一起求。刚开始假了一会，然后仔细思考发现旋转 45∘45 ^ \circ45∘...
前言
会在题目名称后给每道题目一个标记，标 ! 的是我认为非常好的 CNOI-Style 的题，标 * 的是构造题、结论题等比较 Ad-hoc 的题，标 + 的是思维含量比较高题。根据牛牛程度会增减数量。
CF868G El Toll Caves [!!+]
tags: 数学, 数论, 概率论\verb|tags: 数学, 数论, 概率论|tags: 数学, 数论, 概率论
首先最优策略在任意时刻任意两个洞穴被查看的次数之差一定不会超过 222，因此可以得到最优策略是第 iii 论查看 ikikik 到 ik+k−1ik + k - 1ik+k−1 之间的洞穴（模 nnn 意义下）。
然后可以发现将洞穴每 gcd(n,k)\gcd(n, k)gcd(n,k) 个切一段，每段内部的洞穴没有本质区别，因此可以将 n,kn, kn,k 都除掉 gcd(n,k)\gcd(n, k)gcd(n,k)。
考虑设 fif _ ifi 表示宝藏在第 iii 个洞穴内时查看的期望次数，则有：
fi={fi−k+1k≤i<n12+12(fi−k+n+1)0≤i<kf _ i =...
跳过证明，只写做法。
概念
网络（network）是指一张特殊的有向图 G=(V,E)G = (V, E)G=(V,E)。
EEE 中每条边 (u,v)(u, v)(u,v)，有一个被称为流量（capacity）的权值，记作 c(u,v)c(u, v)c(u,v)。若 (u,v)∉E(u, v) \notin E(u,v)∈/E，则可以认为 c(u,v)=0c(u, v) = 0c(u,v)=0。
VVV 中有两个特殊点：源点（source）sss 和汇点（sink）ttt。
对于一张网络 G=(V,E)G = (V, E)G=(V,E)，流（flow）定义为一个从边集到整数集或实数集的函数 f:E→Zf: E \to \mathbb{Z}f:E→Z 或 f:E→Rf: E \to \mathbb{R}f:E→R，其满足如下性质：
容量限制：对于每条边 (u,v)(u, v)(u,v)，流经该边的流量不得超过该边的容量，即 ∀(u,v),0≤f(u,v)≤c(u,v)\forall (u, v), 0 \le f(u, v) \le c(u, v)∀(u,v),0≤f(u,v...
问题描述
给出一个幺半群 (S,⋅)(S, \cdot)(S,⋅) 和元素 u,r∈Su, r \in Su,r∈S，以及一条直线 y=ax+bcy = \frac{a x + b}{c}y=cax+b。
画出平面中所有坐标为正整数的横线和竖线，维护一个 fff，初值为单位元 eee。
从原点出发，先向 yyy 轴正方向走直到到达直线与 yyy 的交点，然后沿直线走一直走到与 x=nx = nx=n 的交点为止。
每当经过一条横线时，执行 f←fuf \gets fuf←fu，经过一条竖线时执行 f←frf \gets frf←fr。特别地，在 yyy 轴上行走时不考虑竖线，同时经过横线和竖线时先执行前者。
求最终的 fff。记为 euclid(a,b,c,n,u,r)\mathrm{euclid}(a, b, c, n, u, r)euclid(a,b,c,n,u,r)。
其中 a,b≥0,n,c>0a, b \ge 0, n, c > 0a,b≥0,n,c>0。
万能欧几里得算法
分情况考虑。
设 m=⌊an+bc⌋m = \lfloor\frac{a...
又名《MK 的第一次坐飞机体验》。
Day -1
上午 9:00 出发去机场。
尝试用手机里的 vim 写了个 A+B（
btw，现在也是用手机里的 vim 在写游记（
总之很快就到机场了。
（为保护当事人隐私，把头挡住了）
不出意外的，飞机延误了（
大概 12:44 的时候上的飞机，机舱内比想象中的要小。
12:59 起飞。人生中第一次坐飞机，感觉飞机太酷了。起飞的时候突然有很大的声音，然后很快速地往前开，上升的时候有很明显的超重感，特别是最开始的一段。
飞过云层的时候中间可以看到一条蓝色的分界线。
（拍得有点糊）
飞的过程中一直都能看到地面，如果没有云的话。
（btw 这张拍得真好看）
（飞机上偷学，右边题目是付费内容所以打码了）
由于一直在颠簸所以一直没饭吃，现在已经 13:50 了还没吃午饭，饿死我了。
然后刚写完这句话就来饭了（
upd：吃完了，锐评一下。
首先我拿到的盒子是这样的：
结果打开来是这样的：
但是，虽然量很少，吃完竟然饱了。
味道还是挺不错的。
后面又做了会题，然后觉得困了就稍微眯了一会，然后飞机就开始降落了。
（重庆...
Link Cut Tree 可以用来维护动态树（树的形态会变化，支持加边删边）的信息。
实链剖分
对于树上每个节点连向儿子的所有边，任意选择至多一条进行剖分。我们称选择的边为实边，连接的儿子为实儿子，其余边为虚边，连接的儿子为虚儿子。
实际上就是任意剖分，因为是任意的所以可以由我们随意改变以满足动态树的要求。
辅助树
对于每一条实链都建一棵 Splay，其中序遍历是该链上点按深度从小到大排序。然后对于每棵 Splay，其根向该实链顶的父亲连一条虚边，这条虚边与 Splay 上的边的区别在于虚边认父不认子，即无法从父亲通过虚边访问儿子。
容易发现可以通过辅助树还原出原树，因此我们只需要维护辅助树而不需要维护原树。
例子：
原树为：
辅助树为：
（图源 OI Wiki）
节点信息
对于辅助树上每个节点，因为是 Splay，所以需要维护父亲 fafafa，左右儿子 son0/1son _ {0 / 1}son0/1，子树大小 sizsizsiz。下面会讲到需要支持 reverse 操作，因此需要维护翻转标记 swpswpswp，以及题目要求的信息。
以上信息在代码中分别记为...